package org.atovio.structure.tree;

import java.io.Serial;
import java.io.Serializable;

/**
 * Huffman树类
 *
 * @author AtoVio, Winter Yuan
 * @version 1.0
 */
public class HuffmanTree implements Serializable {

    @Serial
    private static final long serialVersionUID = 2L;
    // 字符集合
    public final String charset;
    // 静态三叉链表数组
    public final TriElement[] elements;

    /**
     * 根据指定字符集合和权重集合创建Huffman树
     * @param charset 字符集合
     * @param weights 权重集合
     */
    public HuffmanTree(String charset, int[] weights){
        this.charset = charset;
        // 叶子结点
        int n = weights.length;
        // n个叶子结点的Huffman树有2n-1个结点
        this.elements = new TriElement[2 * n - 1];

        // 初始化n个结点
        for (int i = 0; i < n; i++)
            this.elements[i] = new TriElement(weights[i]);
        // 构造n-1个2度结点
        for (int i = n; i < 2 * n - 1; i++) {
            // 将最小值和次小值设为最大整数
            int min1 = Integer.MAX_VALUE;
            int min2 = Integer.MAX_VALUE;
            // 设置二者的下标
            int x1 = -1;
            int x2 = -1;
            // 寻找两个最小的无父母的结点的下标
            for (int j = 0; j < i; j++) {
                if (this.elements[j].parent != -1) {
                    continue;
                }
                // 第j个元素最小
                if (this.elements[j].data < min1) {
                    min2 = min1; // min2记住次小权值
                    x2 = x1; // x2记住次小权值结点下标
                    min1 = this.elements[j].data;
                    x1 = j;
                    // 第j个元素次小
                } else if (this.elements[j].data < min2) {
                    min2 = this.elements[j].data;
                    x2 = j;
                }
            }
            // 合并两棵权值最小的子树
            this.elements[x1].parent = i;
            this.elements[x2].parent = i;
            this.elements[i] = new TriElement(min1 + min2, -1, x1, x2);
        }
    }

    /**
     * 获取charset第i个字符的Huffman编码字符串
     *
     * @param i 字符下标
     * @return 编码字符串
     */
    public String huffmanCode(int i) {
        int n = 16;
        // 声明字符数组暂存Huffman编码
        char[] code = new char[n];
        int child = i;
        int parent = this.elements[child].parent;
        // 由叶结点向上到根结点，反序储存编码
        for (i = n - 1; parent != -1; i--) {
            // 左、右孩子的编码为0，1
            code[i] = (elements[parent].left == child) ? '0' : '1';
            child = parent;
            parent = elements[child].parent;
        }
        return new String(code, i + 1, n - 1 - i);
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder("Huffman树的结点数组：");
        for (TriElement triElement : this.elements)
            str.append(triElement)
                    .append(", ");
        str.append("\nHuffman编码：");
        for (int i = 0; i < this.charset.length(); i++)
            str.append(this.charset.charAt(i))
                    .append(":")
                    .append(huffmanCode(i))
                    .append(", ");
        return str.toString();
    }

    public String decode(String compressed) {
        StringBuilder text = new StringBuilder();
        // node搜索一条从根到达叶子的路径
        int node = this.elements.length - 1;
        for (int i = 0; i < compressed.length(); i++) {
            if (compressed.charAt(i) == '0')
                node = elements[node].left;
            else
                node = elements[node].right;
            // 抵达叶子结点，获取一个字符
            if (elements[node].isLeaf()) {
                text.append(this.charset.charAt(node));
                // 再从根结点开始解码
                node = this.elements.length - 1;
            }
        }
        return text.toString();
    }
}
